package com.atguigu.sort;

import java.util.Arrays;

public class HeapSort {
    //比较器
    public static void comparator(){
        int times=50; //测试次数50次
        int min=10; //最小值为10
        int max=500; //最大值为500
      //  for(int i=0;i<times;i++){
            int[] testArray=new int[100];
            for(int j=0;j<testArray.length;j++){
                testArray[j]=(int)(Math.random()*10000+1000);
            }
            int[] newArray= Arrays.copyOf(testArray,100);
            heapSort(newArray);
            Arrays.sort(testArray);
            for(int k=0;k<100;k++){
                if(newArray[k]==testArray[k]){
                    System.out.print("yes ");
                }else{
                    System.out.print("fuck ");
                }
            }
            System.out.println();
       // }
    }
    public static void main(String[] args) {
        //comparator();
        int[] a=new int[]{23, 98, 78, 5, 51, 34, 86};
        System.out.println(Arrays.toString(a));
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
    public static void heapSort(int[] a){
        if(a.length<2 || a==null){
            return;
        }
        for(int i=0;i<a.length;i++){
            heapInsert(a,i); //O(logN)
        }
        int heapSize=a.length;
        swap(a,0,--heapSize);
        while(heapSize>0){
            heapify(a,0,heapSize); //O(logN)
            swap(a,0,--heapSize); //O(1)
        }
    }
    public static void heapify(int[] a,int index,int heapSize){
        int left=2*index+1; //求出左孩子
        while(left<heapSize){ //存在左孩子
            //先判断有孩子是否存在，如果存在，决出最大值并赋给largest
            int largest=left+1<heapSize && a[left+1]>a[left]?left+1:left;
            //接下来判断左右孩子间的最大值与父节点的大小关系
            if(a[index]<a[largest]){ //父节点小
                swap(a,index,largest); //交换父节点和最大值的节点
                index=largest;  //继续向下遍历
                left=2*index+1;
            }else{ //父节点并不小，这颗子树已经是大根堆了
                break;
            }
        }
    }
    //heapInsert即在index位置插入一个数，然后将该数向上调整
    public static void heapInsert(int[] a,int index){
        while(a[index]>a[(index-1)/2]){
            swap(a,index,(index-1)/2);
            index=(index-1)/2;
        }
    }
    public static void swap(int[] a,int i,int j){
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }
}
